package com.app.util.array;

public class SortUtil {

	public static void bubbleSort(int[] array) {
		int length = array.length - 1;
		for (int out = length; out > 0; out--) {
			for (int in = 0; in < out; in++) {
				if (array[in] > array[in + 1]) {
					int s = array[in];
					array[in] = array[in + 1];
					array[in + 1] = s;
				}
			}
		}
	}
 
	public static void insertSort(int[] array) {
		int length = array.length;
		for (int out = 1; out < length; out++) {
			int temp = array[out];
			int in = out;
			while (in > 0 && array[in - 1] > temp) {
				array[in] = array[in - 1];
				--in;
			}
			array[in] = temp;
		}
	}

	public static void selectSort(int[] array) {
		for (int out = 0; out < array.length - 1; out++) {
			int min = out;
			for (int in = out + 1; in < array.length; in++) {
				if (array[in] < array[min]) {
					min = in;
				}
			}
			int t = array[out];
			array[out] = array[min];
			array[min] = t;
		}
	}

	public class SheelSort {
		private int[] hs;

		private int[] a;

		public void sort() {
			for (int h : hs) {
				for (int i = h; i < a.length; i++) {
					int in = i;
					int inValue = a[i];
					while (in - h > -1 && a[in - h] > inValue) {
						a[in] = a[in - h];
						in = in - h;
					}
					a[in] = inValue;
				}
			}
		}

		public int[] getHs() {
			return hs;
		}

		public void setHs(int[] hs) {
			this.hs = hs;
		}

		public int[] getA() {
			return a;
		}

		public void setA(int[] a) {
			this.a = a;
		}
	}

	public class SpeedSort {
		private int[] a;

		public void sort() {
			int begin = 0;
			int end = a.length - 1;
			quickSort(begin, end);
			for (int i : a) {
				System.out.print(i + " ");
			}
		}

		private void quickSort(int begin, int end) {
			if (begin >= end) {

			} else {
				int pivot = a[end];
				int result = getPivot(begin, end, pivot);
				quickSort(begin, result - 1);
				quickSort(result + 1, end);
			}

		}

		private int getPivot(int begin, int end, int pivot) {
			begin = begin - 1;
			int o = end;
			while (true) {
				while (a[++begin] < pivot) {

				}
				while (end > 0 && a[--end] > pivot) {

				}
				if (begin >= end) {
					break;
				} else {
					swap(begin, end);
				}
			}
			swap(begin, o);
			return begin;
		}

		private void swap(int begin, int end) {
			int t = a[begin];
			a[begin] = a[end];
			a[end] = t;
		}

		public int[] getA() {
			return a;
		}

		public void setA(int[] a) {
			this.a = a;
		}
	}
}
